package binaryTree;

import org.junit.Test;

import java.util.*;

/*
 *@description 单词搜索 II
 *@author hkfan
 *@version 1.0
 *@create 2025/6/24 10:47
 */
public class LeetCode_212 {
    @Test
    public void test(){
        findWords(new char[][]{
                new char[]{'o','a','a','n'},
                new char[]{'e','t','a','e'},
                new char[]{'i','h','k','r'},
                new char[]{'i','f','l','v'}
        },new String[]{"oath","pea","eat","rain"});
    }

    class Node{
        char val;
        int end;
        Map<Character,Node> map;
        String word;

        public Node(char val) {
            this.val = val;
            this.end = 0;
            this.word = "";
            this.map = new HashMap<>();
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        //构建前缀树
        Node root = new Node('0');
        for (String word : words) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                cur.map.putIfAbsent(word.charAt(i),new Node(word.charAt(i)));
                cur = cur.map.get(word.charAt(i));
            }
            cur.end++;
            cur.word=word;
        }

        Set<String> res =new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (root.map.containsKey(board[i][j])){
                    search(board,root,i,j,res);
                }
            }
        }
        return res.stream().toList();
    }

    private void search(char[][] board, Node cur, int i, int j, Set<String> res) {
        if (cur.end>0){
            res.add(cur.word);
//            return;
        }
        if (i<0 || j<0||i>=board.length||j>=board[i].length||board[i][j]=='#'){
            return;
        }
        if (cur.map.containsKey(board[i][j])){
            Node node = cur.map.get(board[i][j]);
            board[i][j]='#';
            search(board,node,i-1,j,res);
            search(board,node,i,j-1,res);
            search(board,node,i+1,j,res);
            search(board,node,i,j+1,res);
            board[i][j]=node.val;
        }
    }
}
